# 46/100 二叉树-二叉树展开为链表
# leetcode第114题: https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/22
from collections import deque
from typing import Optional

from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def flatten(root: Optional[TreeNode]) -> list[int]:
    """使用先序遍历先将节点添加到队列中，然后根据队列顺序重构树结构"""
    order_list = deque()

    def pre_order(node: Optional[TreeNode]):
        nonlocal order_list
        if node:
            order_list.append(node)
            pre_order(node.left)
            pre_order(node.right)

    pre_order(root)
    if order_list:
        curr, curr.left, curr.right = order_list.popleft(), None, None
        while order_list and curr:
            curr.right, curr.left = order_list.popleft(), None
            curr = curr.right

    return TreeConverter.tree_to_list(root)


def flatten_opt(root: Optional[TreeNode]) -> list[int]:
    """使用先序遍历先将节点添加到队列中，然后根据队列顺序重构树结构"""
    if not root:
        return []

    stack = [root]
    prev = None

    while stack:
        curr = stack.pop()
        if prev:
            prev.left = None
            prev.right = curr
        left, right = curr.left, curr.right
        if right:
            stack.append(right)
        if left:
            stack.append(left)
        prev = curr

    return TreeConverter.tree_to_list(root)


def flatten_o1(root: Optional[TreeNode]) -> list[int]:
    """一种空间复杂度为1的方法
    使用前序遍历访问各节点，如果一个节点的左子节点为空，则不影响前序遍历的顺序，无需进行操作；
    如果一个节点的左子节点不为空，则左子树中最后一个节点被访问后才访问该节点的右子树，所以可以定义该左子树中最后一个被访问的节点为右子树的前驱节点pre。
    在找到前驱节点后，则将整个右子树作为前驱节点的右子树即可
    next指针则指向当前节点curr的下一个先序遍历的节点
         1             1           1               1          1
        / \           /             \               \          \
       2   5         2               2               2          2
      /\    \       / \             / \             /            \
     3  4    6     3   4           3   4           3              3
                        \               \           \              \
                         5               5           4              4
                          \               \           \              \
                           6               6           5              5
                                                        \              \
                                                         6              6
    """
    curr = root
    while curr:
        if curr.left:
            pre = nxt = curr.left  # pre 为前驱节点
            while pre.right:
                pre = pre.right
            pre.right = curr.right
            curr.left = None
            curr.right = nxt
        curr = curr.right
    return TreeConverter.tree_to_list(root)


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([1, 2, 5, 3, 4, None, 6])
    t2 = TreeConverter.list_to_tree([])
    t3 = TreeConverter.list_to_tree([0])
    t4 = TreeConverter.list_to_tree([])
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, {"root": t4}, ]
    out = [[1, None, 2, None, 3, None, 4, None, 5, None, 6], [], [0], []]
    test.test_function(flatten, inp, out)
    test.test_function(flatten_opt, inp, out)
    test.test_function(flatten_o1, inp, out)
